package problem68_Text_Justification;

import java.util.LinkedList;
import java.util.List;

public class MySolution {
	public static void main(String[] args){
		List<String> res=new MySolution().fullJustify(new String[]{"What","must","be","shall","be."}, 12);
		System.out.println(res.get(0).length());
	}
	
	public List<String> fullJustify(String[] words, int maxWidth) {
		List<String> result=new LinkedList<>();
		int start=0;
		while(start<words.length){
			int currentLength=words[start].length(),end=start;
			if(currentLength>maxWidth) return null;
			while(currentLength<=maxWidth){
				if(++end<words.length){
					currentLength+=(1+words[end].length());
				}else{
					break;
				}
			}
			result.add(buildStringWithSpace(start,end-1,words,maxWidth));
			start=end;
		}
		return result;
    }
	
	private String buildStringWithSpace(int start,int end,String[] words,int strLength){
		String result=words[start];
		if(end==words.length-1){
			int i=start+1;
			while(result.length()<strLength){
				result+=(i<=end?" "+words[i++]:" ");
			}
		}else if(start==end){
			for(int i=words[start].length();i<strLength;i++){
				result+=" ";
			}
		}else{
			int wordsLen=0;
			for(int i=start;i<=end;i++){
				wordsLen+=words[i].length();
			}
			int avgNumOfSpaces=(strLength-wordsLen)/(end-start);
			String spaces="";
			for(int i=0;i<avgNumOfSpaces;i++){
				spaces+=" ";
			}
			int reminder=(strLength-wordsLen)%(end-start);
			for(int i=start+1;i<=end;i++){
				result+=(spaces+(reminder--<=0?"":" ")+words[i]);
			}
		}
		return result;
	}
	
}
